package com.leetcode;


/**
 * 1247. 交换字符使得字符串相同 (中等)
 * 有两个长度相同的字符串s1 和s2，且它们其中只含有字符"x" 和"y"，你需要通过「交换字符」的方式使这两个字符串相同。
 * 每次「交换字符」的时候，你都可以在两个字符串中各选一个字符进行交换。
 * 交换只能发生在两个不同的字符串之间，绝对不能发生在同一个字符串内部。也就是说，我们可以交换s1[i] 和s2[j]，但不能交换s1[i] 和s1[j]。
 * 最后，请你返回使 s1 和 s2 相同的最小交换次数，如果没有方法能够使得这两个字符串相同，则返回-1 。
 */
public class LeetCode1247 {

    public static void main(String[] arg0) {
        String testStr1 = "yxyxxxyyxxyxxxx";
        String testStr2 = "yyyxyyyxyxxxyxy";
        System.out.println("使 s1 和 s2 相同的最小交换次数 = " + minimumSwap(testStr1, testStr2));
    }

    /**
     *
     */
    public static int minimumSwap(String s1, String s2) {
        StringBuilder tempS1 = new StringBuilder();
        StringBuilder tempS2 = new StringBuilder();
        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i) != s2.charAt(i)) {
                tempS1.append(s1.charAt(i));
                tempS2.append(s2.charAt(i));
            }
        }

        System.out.println("tempS1 == " + tempS1 + "， tempS2 == " + tempS2);
        int res = 0;
        int length = tempS1.length();
        if (length % 2 == 0) {
            int count = 0;
            String[] lastData = getLastString(tempS1.toString(), count);
            System.out.println("last count = " + lastData[1]);
            if (lastData[0].length() == 0) {
                res = Integer.parseInt(lastData[1]);
            } else {
                res = ((lastData[0].length() - 1) / 4 + 1) * 2 + Integer.parseInt(lastData[1]);
            }
        } else {
            res = -1;
        }

        return res;
    }

    public static String[] getLastString(String str, int count) {
        String tempStr = "";
        int preend = 0;
        for (int i = 1; i < str.length(); i++) {
            int start = i - 1;
            int end = i;
            while (start >= preend && end < str.length() && str.charAt(start) == str.charAt(end)) {
                count++;
                start--;
                end++;
            }
            if ((end - start) > 1) { // 代表有消掉的元素，tempStr记录剩余元素
                tempStr += str.substring(preend, start + 1);
                preend = end;
            }
            i = end;
        }

        if (preend < str.length()) {
            tempStr += str.substring(preend);
        }

        System.out.println("str = " + str + ", tempStr = " + tempStr + ", count = " + count);
        if (tempStr.length() == str.length()) {
            return new String[]{tempStr, String.valueOf(count)};
        } else {
            return getLastString(tempStr, count);
        }
    }


}
